﻿public class Solution
{

    private IList<string> res = new List<string>();
    
    public IList<string> RestoreIpAddresses(string s)
    {
        int startIndex = 0;
        int pointNum = 0;
        trackbacking(s, startIndex, pointNum);
        return res;
    }

    private void trackbacking(string s, int startIndex, int pointNum)
    {
        if (pointNum == 3)
        {
            if (IsValid(s, startIndex, s.Length - 1))
            {
                res.Add(s);
            }
            return;
        }

        for (int i = startIndex; i < s.Length; i++)
        {
            if (IsValid(s, startIndex, i))
            {
                s = s.Insert(i + 1, ".");
                pointNum++;
                trackbacking(s, i+2, pointNum);
                pointNum--;
                s = s.Remove(i + 1, 1);
            }
        }
    }

    private bool IsValid(string s, int startIndex, int endIndex)
    {
        if (startIndex > endIndex) return false;
        if (s[startIndex] == '0' && endIndex != startIndex) return false;

        int num = 0;
        for (int i = startIndex; i <= endIndex; i++)
        {
            int n = s[i] - '0';
            if (n < 0 || n >= 10) return false;
            num = num * 10 + n;
        }

        if (num > 255 || num < 0) return false;
        return true;
    }

    public static void Main(string[] args)
    {
        string s = "101023";
        Solution solution = new Solution();
        IList<string> res = solution.RestoreIpAddresses(s);
        foreach (string r in res)
        {
            Console.WriteLine(r);
        }
    }
}